yukicoder contest 369 E
（工事中）
解き方
※ ここに書く解き方は、解説に書かれているTester 解とほぼ同様であるが計算量の見積もりが少し異なる まずは
$ 0 と$ 1 のみからなる長さ$ M の列
辞書順でソートしたときに、隣り合うものが異なる個数
原子集合 $ S \subseteq \mathcal{P}(X) $ \mathrm{Atom}(S) $ A \in S が下の条件を満たすとき、$ A は$ S の原子集合である
$ A \in S が$ S の原子集合である $ \iff \forall A^{\prime} \in S \setminus \{ \empty, A \}. ~~ A^{\prime} \not\subseteq A を満たすとき、$ A は$ S の原子集合であるとする
$ S \subseteq \mathcal{P}(X) が、問題文に書かれた良い集合の条件を満たすとすると、以下の
$ S の原子集合はpairwise disjoint である。すなわち、$ \forall A_{1}, A_{2} \in \mathrm{Atom}(S). ~~ \left( A_{1} \neq A_{2} \Rightarrow A_{1} \cap A_{2} = \empty \right) が成り立つ。
$ S の原子集合全ての和集合は$ X に一致する。すなわち、$ \bigcup_{A \in \mathrm{Atom}(S)} A = X が成り立つ。
$ \mathcal{S} \subseteq \mathcal{P}(X)
解いたのが結構前だから、Tester 解との違いとか、ここで書こうとしていたことが思い出せない、、、
解説と自分の提出を見比べていたが、Tester 解と何が違う、、、？
$ O(NM \log N) の計算量では？ということかな、Tester との違い
集合族（冪集合の部分集合）$ S \subseteq \mathcal{P}(X) に対し、$ S の原子集合を下記のように定義する。
$ A \in S が$ S の原子集合である $ \iff \forall A^{\prime} \in S \setminus \{ \empty, A \}. ~~ A^{\prime} \not\subseteq A を満たす
※ この原子集合という概念は、この記事における説明の都合上定義したものであり
※ この原子集合という概念は、この記事における説明のため導入したものであり。一般的に使われる概念ではないことに注意すること
集合族\mathrm{Atom}(S)
$ S \subseteq \mathcal{P}(X) が、問題文に書かれた良い集合の条件を満たすとすると、$ S の原子集合について以下の条件が成り立つ。
$ S \subseteq \mathcal{P}(X) が、問題文に書かれた良い集合の条件を満たすとすると、$ S の原子集合について以下が成り立つ。
$ S の原子集合はpairwise disjoint である。すなわち、$ \forall A_{1}, A_{2} \in \mathrm{Atom}(S). ~~ \left( A_{1} \neq A_{2} \Rightarrow A_{1} \cap A_{2} = \empty \right) が成り立つ。
また、$ S の原子集合全ての和集合は$ X に一致する。すなわち、$ \bigcup_{A \in \mathrm{Atom}(S)} A = X が成り立つ。